package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         236,
		Discription: "二叉树的最邻近祖先",
		Level:       2,
		Labels: map[string]int{
			"二叉树": 1,
			"回溯":  1,
		},
	})
}

// 返回表示该子树下有无p或q
func LowestCommonAncestor2(root, p, q *ds.TreeNode) *ds.TreeNode {
	if root == nil {
		return nil
	}

	//两种情况
	//另一个节点也在该子树下，则root是最邻近祖先，返回root
	//另一个节点不在该子树下，返回root表示该子树下有p或q的一个节点
	if root.Val == p.Val || root.Val == q.Val {
		return root
	}

	left := LowestCommonAncestor2(root.Left, p, q)
	right := LowestCommonAncestor2(root.Right, p, q)
	//p q刚好分列左右子树
	if left != nil && right != nil {
		return root
	}

	//都在左子树，或左子树有其中一个
	if left != nil {
		return left
	}

	//都在右子树，或右子树有其中一个
	if right != nil {
		return right
	}

	//都不在
	return nil
}
